package com.ctrip.study.algorithm.pratice;

import org.junit.Test;
import org.springframework.stereotype.Controller;

import junit.framework.TestCase;

/**
 * 判断整数序列是不是二元查找树的后序遍历结果.
 */
public class ArrayVerifyBSTPostSort extends TestCase{

	@Test
	public void test(){
		int[] array = {5, 7, 6, 9, 11, 10, 8};
		boolean result = judgeBSTPostSort(array);
		assertTrue(result);
	}

	/**
	 * 在后续遍历得到的序列中，
	 * 最后一个元素为树的根结点。
	 * 从头开始扫描这个序列，
	 * 比根结点小的元素都应该位于序列的左半部分；
	 * 从第一个大于跟结点开始到跟结点前面的一个元素为止，
	 * 所有元素都应该大于跟结点，
	 * 因为这部分元素对应的是树的右子树。
	 * 根据这样的划分，把序列划分为左右两部分，
	 * 我们递归地确认序列的左、右两部分是不是都是二元查找树。
	 */
	private boolean judgeBSTPostSort(int[] array) {
		return judge(array, array.length);
	}

	private boolean judge(int[] array, int length) {
		// 判断数组是否为空或长度为0  
	    if(array == null || length <= 0){
	    	return false;
	    }
	    // 后序排序二叉树的根节点是数组的最后一个，这是后序排序的特点  
	    int root = array[length - 1];
	    // 左子树的值永远要小于根节点，
	    // 否则就可以判定该数组序列不是后序排序的二叉树  
	    // squence[i]>root表明此时squence[i]进入右子树区间  
	    int leftTreeLength = 0;  
	    while(leftTreeLength < length && array[leftTreeLength] < root){
	    	leftTreeLength++;
	    }
	    // 右子树的值永远要大于根节点，
	    //否则就可以判定该数组序列不是后序排序的二叉树  
	    // j = i 继续检查右子树  
	    int j = leftTreeLength;  
	    for(; j < length - 1; ++j)  
	    {  
	        if(array[j] < root)  
	            return false;  
	    }  
	    // 在区间点i，继续对两个区间检查  
	    // left和right的初值不能设定为false，这是要考虑到区间为一个数值的情况。  
	    // 区间为一个值时，上面2个for循环已经不起作用了，并且下面2个if语句为false  
	    // 此时如果left，right的初值设为false，则区间为一个值时就会返回false，导致判断出错。  
	    boolean left = true;   
	    if(leftTreeLength > 0)  
	        left = judge(array, leftTreeLength);  
	    boolean right = true;  
	    if(leftTreeLength < length - 1)  
	        right = judge(array, length - leftTreeLength - 1);  
	    return(left && right);
	}

}
